Remove duplicates from sorted array [Two pointers]

Time: O(N); Space: O(1); easy

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

Example 1:

Input: A = [1, 1, 2],

Output: 2, and A is now [1, 2].

Example 2:

Input: A = [0,0,1,1,1,2,2,3,3,4]

Output: 5, and A is now [0, 1, 2, 4].

Notes:

  • It doesn’t matter what you leave beyond the returned length.

Clarification

Confused why the returned value is an integer but your answer is an array? Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this: // nums is passed in by reference. (i.e., without making a copy) len = removeDuplicates(nums) // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for i in range(len): print(nums[i])

Algorithm Since the array is already sorted, we can keep two pointers ii and jj, where i is the slow-runner while j is the fast-runner. As long as nums[i] = nums[j], we increment j to skip the duplicate.

When we encounter nums[j] <> nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until jj reaches the end of array.

Hints:

  1. In this problem, the key point to focus on is the input array being sorted. As far as duplicate elements are concerned, what is their positioning in the array when the given array is sorted? Look at the image above for the answer. If we know the position of one of the elements, do we also know the positioning of all the duplicate elements?

  2. We need to modify the array in-place and the size of the final array would potentially be smaller than the size of the input array. So, we ought to use a two-pointer approach here. One, that would keep track of the current element in the original array and another one for just the unique elements.

  3. Essentially, once an element is encountered, you simply need to bypass its duplicates and move on to the next unique element.

[3]:

class Solution1(object):
    """
    Time: O(n). Assume that nn is the length of array. Each of i and j traverses at most N steps.
    Space: O(1).
    """
    def removeDuplicates(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0

        last, i = 0, 1
        while i < len(A):
            if A[last] != A[i]:
                last += 1
                A[last] = A[i]
            i += 1

        return last + 1

[4]:

s = Solution1()
A = [1, 1, 2]
assert s.removeDuplicates(A) == 2
print(A)

A = [0,0,1,1,1,2,2,3,3,4]
assert s.removeDuplicates(A) == 5
print(A)

[1, 2, 2]
[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]